#include "hash.h"
#include <stdlib.h>
#define MAXSTEP 10000

// 0 1 2 
// 3 4 5
// 6 7 8

enum Mov {UP, LEFT, RIGHT, DOWN};

enum Mov progress[MAXSTEP];

int Operate (int list[MAXINT], enum Mov k);

void Process (int listp[MAXINT], int deep);

int Des[MAXINT] = {1,2,3,4,5,6,7,8,0}, DesValue, over = 0, num = 0, model = 0;

int Pile = 0;

node * head = NULL, * tail = NULL;

void PutInFrontier (int list[MAXINT], int deep);

void PrintFrontier (void);

int SearchForBest (int list[MAXINT]);

int CheckIfTransable (int list[MAXINT]);

int CheckIfTransable (int list[MAXINT])
{
    int typetran1 = 0, typetran2 = 0;
    typetran2 = 26;
    for(int i = 0;i < MAXINT;i++)
        for(int j = 0;j < i;j++)
            if(list[j] < list[i])
                typetran1++;
    if((typetran1 - typetran2) % 2)
        return 0;
    else
        return 1;
}

int main (void)
{
    int rand (void);
    void InitState (void);
    head = malloc(sizeof(node));
    tail = head;
    head->next = head->pre = NULL;
    int list[MAXINT] = {0,1,3,4,2,5,7,8,6};
    int sp = 0;
    printf("Please input model:\n0--H1 1--H2\n");
    scanf("%d",&model);
    model = 1-model;

    DesValue = HashValue(Des);

    printf("\nPre handling your hash table...\n");
    PreHandlePath();
    printf("Pre handle complete.\n");

    while(sp++ < 20){   
        InitState();
        int jk = Path[rand()].list;
        for(int i = 0;i < MAXINT;i++)
            list[i] = jk % 10, jk /= 10;
        printf("###########################\n初始状态:\n");
        for(int i = 0;i < MAXINT;i++)
            printf("%d ",list[i]);
        if(!CheckIfTransable(list))
        {
            printf("\n这种初始情况没有解！\n###########################\n");
            continue;
        }
        Process(list,0);
        printf("###########################\n");
    }
}

void Process (int list[MAXINT], int deep)
{
    void Record (enum Mov dir);
    void Unrecord (void);
    int result; 
    if(over) return ;
    int NowValue = HashValue(list);
    if(NowValue == DesValue)
    {
        printf("\nGuessed");
        printf("启发式层数：%d\n",deep);
        node * p = head->next;
        while(p)
            p = p->next, num++;
        printf("生成结点个数：%d\n",num);
        over = 1;
        return ;
    }else if(Path[NowValue].record)
        return ;
    Path[NowValue].record = 1;
    //记录路径
    for(int i = 0;i < 4;i++)
    {
        result = Operate(list,i);
        NowValue = HashValue(list);
        //模拟移动，将其加入边界
        if(result && !Path[NowValue].record)
            PutInFrontier(list,deep);
        if(result)
            Operate(list,3-i);
    }
    int depth = SearchForBest(list);
    //在边界集合中寻找出最好的解
    Process(list,depth+1);
    //用该解继续搜索
}

int SearchForBest (int list[MAXINT])
{
    node * p = head->next;
    if(!p) {printf("Error! Fifo empty!\n"); return -1;}
    int Min = HASHSIZE, NextTry, depth;
    while(p)
    {
        if(((model)?p->Hvalue1:p->Hvalue2) + p->deep < Min)
            Min = p->deep + ((model)?p->Hvalue1:p->Hvalue2);
        p = p->next;
    }
    p = head->next;
    while(p)
    {
        //printf("value: %d+%d\n",p->Hvalue1, p->deep);
        if(((model)?p->Hvalue1:p->Hvalue2) + p->deep == Min)
        {
            NextTry = p->list;
            if(p->next) p->next->pre = p->pre;
            else tail = p->pre;
            p->pre->next = p->next;
            depth = p->deep;
            free(p);
            break ;
        }else
            p = p->next;
    }
    for(int i = 0;i < MAXINT;i++)
    {
        list[MAXINT-i-1] = NextTry % 10;
        NextTry /= 10;
    }
    //printf("-----------------------------------\n");
    //printf("d %d: %d %d %d %d %d %d %d %d %d\n",depth,list[0],list[1],list[2],list[3],list[4],list[5],list[6],list[7],list[8]);
    //printf("-----------------------------------\n");
    num++;
    return depth;
}

void PutInFrontier (int list[MAXINT], int deep)
{
    //printf("PUTING %d %d %d %d %d %d %d %d %d in frontier\n",list[0],list[1],list[2],list[3],list[4],list[5],list[6],list[7],list[8]);
    node * q = head->next;
    int hash = HashValue(list);
    while(q)
    {
        if(q->hash == hash)
        {
            q->deep = (deep < q->deep)? deep: q->deep;
            //printf("Updating depth\n");
            return ;
        }
        //倘若在frontier中已经存在想要添加的结点则更新deep
        q = q->next;
    }
    node * p = malloc(sizeof(node));
    p->hash = hash;
    p->Hvalue1 = Path[p->hash].Hvalue1;
    p->Hvalue2 = Path[p->hash].Hvalue2;
    p->list = ListValue(list);
    p->next = NULL;
    p->deep = deep;
    tail->next = p;
    p->pre = tail;
    tail = tail->next;
    //printf("\n#######################\n");
    //PrintFrontier();
    //printf("#######################\n\n");
}

void PrintFrontier (void)
{
    node * p = head->next;
    while(p)
    {
        if(p->list < 100000000)
            printf("0");
        printf("%d\n",p->list);
        p = p->next;
    }
}

int Operate (int list[MAXINT], enum Mov k)
{
    int Pos, temp;
    for(int i = 0;i < MAXINT;i++)
        if(list[i] == 0)
            Pos = i;
    if(k == UP)
    {
        if(Pos < 3) return 0;
        temp = list[Pos];
        list[Pos] = list[Pos-3];
        list[Pos-3] = temp;
    }else if(k == LEFT)
    {
        if(Pos%3 == 0) return 0;
        temp = list[Pos];
        list[Pos] = list[Pos-1];
        list[Pos-1] = temp;
    }else if(k == DOWN)
    {
        if(Pos > 5) return 0;
        temp = list[Pos];
        list[Pos] = list[Pos+3];
        list[Pos+3] = temp;
    }else if(k == RIGHT)
    {
        if(Pos%3 == 2) return 0;
        temp = list[Pos];
        list[Pos] = list[Pos+1];
        list[Pos+1] = temp;
    }
    return 1;
}

void InitState (void)
{
    over = 0;
    tail = head;
    free(head->next);
    free(head->pre);
    head->next = head->pre = NULL;
    num = 0;
    for(int i = 0;i < 362880;i++)
        Path[i].record = 0;
    Pile = 0;
}